The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
I. Border Gateway Protocol
Border Gateway Protocol (BGP) is an exterior gateway protocol (EGP) that is used to exchange routing information among network elements (usually routers) in autonomous systems and networks. A network element that executes a BGP process is typically referred to as a BGP host or a BGP speaker.
In order to exchange BGP routing information, BGP speakers exchange initial messages to establish a transport protocol connection with one another and to open a BGP session. Once a BGP session is open, a BGP speaker and its peers exchange routing information. During the initial connection setup, the BGP speakers exchange all the routing information that each one maintains, possibly limited according to policy filters [jgs□□□•□□□1]. The routing information sent from a BGP speaker includes the complete routing information to each network destination reachable from the BGP speaker. Typically, the routing information includes the address prefix of the destination location (also referred to as a “prefix”) and the attributes that describe the path to the destination host. At each host, the routing information is stored in a Routing Information Base (“RIB”). Generally, a BGP RIB is implemented as a single physical routing table.
Once the initial setup has been made, updates to the routing information are exchanged, or advertised, between peers for the remainder of the session.
During the initial setup of a BGP session, the amount of data exchanged between peer speakers can be significant, especially on larger networks. Hence, the amount of computing, bandwidth and network resource overhead to set up a BGP session may be very significant. [jgs□□□•□□□2].
After a BGP session has been established, if a router participating in the session restarts or otherwise stops participating in the session, then the other router which was participating in the session (the “peer”) will purge from its RIB all routes that were advertised as reachable by the unavailable router. When the BGP host becomes available again, every BGP speaker with which it communicates, or “peers”, has to exchange routing information and recreate routing tables as if the BGP host is a brand new entity to the network. During the time required to perform such an exchange and re-create the tables (“re-convergence time”), a particular BGP host may be unable to forward data to peers on the previously unavailable routes. Since BGP is often deployed at WAN edges, the effect of an unavailable BGP host can propagate across multiple networks, disrupting more than one domain and one network.
Under these circumstances, the process of re-converging routing table information is time-consuming. In addition, the amount of computing resources and the consumption of network bandwidth required to resynchronize routing information can degrade network performance. In some cases, it may even cause temporary outages of services.
Accordingly, some techniques have been introduced to reduce this problem. Graceful Restart is one such behavior added to BGP to improve re-convergence issues after a BGP host restarts.
II. Graceful Restart
Graceful Restart (“GR”) logic can reduce the duration and effect of outages associated with a failed BGP process. GR is defined in an IETF INTERNET DRAFT entitled “Graceful Restart Mechanism for BGP”. To reduce the effect of outages associated with a failed BGP process, GR behavior is incorporated on a BGP host and its peers. When an initial BGP connection is established, both the restarting router and its peers exchange messages indicating that they support GR capability. The restarting router and its peers exchange capability negotiation messages including the BGP capability code “64,” which notifies peers that the sending BGP speaker understands GR.
GR logic prevents BGP speakers from immediately purging routing information from their tables when a peer becomes unavailable. Instead, under GR logic the peer speakers hold routes associated with the restarting speaker in a “stale” state for a negotiated timeframe. In addition, with GR logic a restarting BGP speaker informs its peers that the restarting speaker is still in a forwarding state and, hence, the restarting speaker can continue to receive and forward packets.
Thus, when a restarting speaker restarts and opens a new BGP session, the restarting speaker sends messages with flags set that notify its peers that the BGP process with extended GR capabilities has restarted. As a result, the peer speakers send all their routing information and updates to the restarting speaker.
The restarting speaker determines that it has finished receiving updates from a peer when it receives an End-of-RIB (“EOR”) marker. Typically, the EOR marker is an empty BGP update message. The restarting speaker then begins best-path selection using the new routing information. Once the restarting speaker has recomputed its routing tables, the restarting speaker sends updates to its peers. The peers recalculate their routing tables, send updates, etc. This process continues until the network has re-converged. Notably, with GR forwarding is not impacted during re-convergence, and peers not in direct communication with the failed router are not affected by the re-convergence.
Although GR improves re-convergence time, resynchronization of routing information still takes too long and consumes too many resources to be effective in certain situations. For example, in military and mobile situations, the exchange of routing information should consume as little bandwidth as possible. Yet, after a restart, peers still send all their routing information to the restarting speaker regardless of what has taken place during the restart process and regardless of what routing information the restarting speaker already holds.
For example, a restarting speaker may come back online before any changes have been made to any peer routing tables. Under GR, the restarting speaker is still flooded by routing update messages once it comes online. As another example, assume only a few changes have been made to peer routing information. When the restarting router comes back online, again, the restarting speaker is flooded by routing update messages from its peers even though there have been few changes. Accordingly, one of the main drawbacks to GR is that peers exchange non-essential and redundant information.
BGP is also sometimes used with mobile packet routing devices that communicate using wireless links. For example, some military organizations use routers in field environments in which the routers are periodically moved to different locations. Such moves can result in one mobile router temporarily losing connectivity to a peer, which may be stationary or mobile. Normally, under BGP and TCP a loss of connectivity results in tearing down a BGP session and terminating the underlying TCP connection. However, in such mobile applications, conservation of resources such as CPU use, network bandwidth, and power are important. The processing overhead of setting up and tearing down BGP sessions and TCP connections among mobile devices is considered costly. Therefore, a need exists for a way to minimize the use of resources when mobile devices are moved and lose connectivity.
Further, in such mobile applications, a need sometimes exists to temporarily cease wireless network communications among the mobile devices. Temporarily ceasing communications may be termed “radio silence” or operating in “covert mode.” In such a mode, a mobile device can receive data relating to BGP sessions and TCP connections wirelessly, or receive other data for command and control functions, but cannot transmit data, which would result in emitting radio-frequency energy. There is a need for mobile devices to run protocols such as BGP and TCP while accommodating periods of “radio silence” or “covert mode,” without tearing down the BGP sessions or TCP connections.